#include <stdio.h>
#include <stdlib.h>
//线索二叉树之中序线索二叉树
typedef char ElemType;
//1️⃣线索二叉树结点的声明
typedef struct bitree
{
    ElemType data;
    struct bitree *lchild;
    struct bitree *rchild;
    int ltag;
    int rtag;
}BiTree;
char expr[]="ABDH##I##E#J##CF##G##"; //P155  这是按照前序顺序写的
//中序遍历顺序：HDIBEJAFCG
int i=0;
//2️⃣创建线索二叉树：按照前序顺序创建的
void creatbitree(BiTree **t)
{
    ElemType symbol=expr[i++];
    if(symbol=='#')
    {
        *t=NULL;
    }
    else
    {
        *t=(BiTree *)malloc(sizeof(BiTree));
        (*t)->data=symbol;
        creatbitree(&(*t)->lchild); //()优先级 > ->优先级 > &优先级
        if((*t)->lchild!=NULL)
        {
            (*t)->ltag=0;    //有树
        }
        creatbitree(&(*t)->rchild);
        if((*t)->rchild!=NULL)
        {
            (*t)->rtag=0;   //有树
        }
    }
}
BiTree *pre; //记录访问的上一个节点
//3️⃣中序线索化（递归）  P155
//②具体线索化：按照中序顺序，所以对于正在访问(正在放线索)的结点来说，pre就是中序顺序中它的前一个元素
//            pre变化顺序就是中序顺序
void threading(BiTree *t)
{
    if(t!=NULL)
    {
        threading(t->lchild);
        if(t->lchild==NULL)
        {
            t->ltag=1;
            t->lchild=pre;
        }
        if(pre->rchild==NULL)
        {
            pre->rtag=1;
            pre->rchild=t;
        }
        pre=t;
        threading(t->rchild);
    }
}
//①开始线索化
void cluebitree(BiTree **head,BiTree *t)
{
    *head=(BiTree *)malloc(sizeof(BiTree));//第一步：创建头节点
    if(t==NULL)
    {
        (*head)->lchild=(*head);
    }
    else
    {
        //第二步：让头节点左孩子指向根节点，并使ltag=0，rtag=1
        (*head)->data=0;
        (*head)->lchild=t;
        (*head)->rchild=(*head); //这里不能初始化为NULL，因为具体线索化时要作为判断条件
        (*head)->ltag=0;
        (*head)->rtag=1;
        pre=(*head);   //初始化成头节点是为了在具体线索化时可以使中序顺序的第一个元素的左孩子指向头节点
        //第三步：开始放线索——具体线索化
        threading(t);
        //具体线索化完成后pre指向中序顺序中最后一个元素
        //第四步：给最后一个元素右边线索化
        //因为具体线索化是在遍历下一个元素时才会给上一个元素的右孩子放线索（这里的上下是指中序顺序）
        //所以最后一个元素只有左边有线索
        pre->rchild=(*head);  //让最后一个元素的右孩子指向头节点
        pre->rtag=1;     
        //第五步：让头节点的右孩子指向最后一个元素
        (*head)->rchild=pre;
    }
}
//4️⃣基于线索中序遍历：类似于对双向链表遍历
void inbitree(BiTree *head)
{
    pre=head->lchild;
    while(pre!=head)
    {
        while(pre->ltag==0)
        {
            pre=pre->lchild;
        }        //一直找到最左边的孩子即中序顺序第一个元素
        printf("%c",pre->data);
        while(pre->rtag==1&&pre->rchild!=head)
        {
            pre=pre->rchild;
            printf("%c",pre->data);
        }
        pre=pre->rchild;   //P157
    }
}
int main()
{
    BiTree *t=NULL;
    //创建线索二叉树
    creatbitree(&t);
    //线索化
    BiTree *head=NULL;
    cluebitree(&head,t);  //二叉树创建好了但要将线索存进去
    //这里还是一个二级指针，因为在函数内要改变head的值，类似于前面出栈保留出栈元素
    //基于线索中序遍历
    inbitree(head);
    return 0;
}
//输出：HDIBEJAFCG
//总结一下：
//创建线索二叉树：要使用二级指针，原因可看27erchashu.c，并判断是否有树（放0）
//线索化：也使用了二级指针；分成开始和具体两部分，开始主要与头结点的连接有关，具体主要使用递归方法给节点放线索
//具体线索化：根据中序顺序，让某结点左孩子指向前一个元素，右孩子指向后一个元素
//遍历：由于结点右孩子指向下一个元素，所以找到第一个元素后，用循环的方法一直找右孩子